import java.util.ArrayList;
import java.util.List;
import java.util.Random;
import java.util.Scanner;

public class HillCipher {
    private int[][] keyMatrix;
    private int[][] inverseKeyMatrix;
    private int matrixSize;
    
    public HillCipher(int size) {
        this.matrixSize = size;
        generateKeyMatrix();
        calculateInverseMatrix();
    }
    
    // 1. 密钥生成
    private void generateKeyMatrix() {
        Random random = new Random();
        keyMatrix = new int[matrixSize][matrixSize];
        
        while (true) {
            // 生成随机矩阵
            for (int i = 0; i < matrixSize; i++) {
                for (int j = 0; j < matrixSize; j++) {
                    keyMatrix[i][j] = random.nextInt(26);
                }
            }
            
            // 检查行列式是否可逆
            if (isMatrixInvertible(keyMatrix)) {
                break;
            }
        }
        
        System.out.println("生成的密钥矩阵:");
        printMatrix(keyMatrix);
    }
    
    // 检查矩阵在模26下是否可逆
    private boolean isMatrixInvertible(int[][] matrix) {
        int det = calculateDeterminant(matrix) % 26;
        if (det < 0) det += 26;
        return gcd(det, 26) == 1;
    }
    
    // 计算行列式
    private int calculateDeterminant(int[][] matrix) {
        if (matrix.length == 2) {
            return matrix[0][0] * matrix[1][1] - matrix[0][1] * matrix[1][0];
        } else if (matrix.length == 3) {
            return matrix[0][0] * (matrix[1][1] * matrix[2][2] - matrix[1][2] * matrix[2][1])
                 - matrix[0][1] * (matrix[1][0] * matrix[2][2] - matrix[1][2] * matrix[2][0])
                 + matrix[0][2] * (matrix[1][0] * matrix[2][1] - matrix[1][1] * matrix[2][0]);
        }
        // 对于更大的矩阵需要更复杂的实现
        return 0;
    }
    
    // 计算最大公约数
    private int gcd(int a, int b) {
        if (b == 0) return a;
        return gcd(b, a % b);
    }
    
    // 计算模逆元
    private int modInverse(int a, int m) {
        a = a % m;
        for (int x = 1; x < m; x++) {
            if ((a * x) % m == 1) {
                return x;
            }
        }
        return 1;
    }
    
    // 2. 计算逆矩阵
    private void calculateInverseMatrix() {
        int det = calculateDeterminant(keyMatrix) % 26;
        if (det < 0) det += 26;
        int detInverse = modInverse(det, 26);
        
        if (matrixSize == 2) {
            inverseKeyMatrix = new int[2][2];
            // 伴随矩阵
            inverseKeyMatrix[0][0] = keyMatrix[1][1];
            inverseKeyMatrix[0][1] = (-keyMatrix[0][1] + 26) % 26;
            inverseKeyMatrix[1][0] = (-keyMatrix[1][0] + 26) % 26;
            inverseKeyMatrix[1][1] = keyMatrix[0][0];
            
            // 乘以行列式的逆
            for (int i = 0; i < 2; i++) {
                for (int j = 0; j < 2; j++) {
                    inverseKeyMatrix[i][j] = (inverseKeyMatrix[i][j] * detInverse) % 26;
                }
            }
        } else if (matrixSize == 3) {
            // 3x3矩阵的逆矩阵计算（简化版）
            inverseKeyMatrix = calculate3x3Inverse(keyMatrix, detInverse);
        }
        
        System.out.println("计算的逆矩阵:");
        printMatrix(inverseKeyMatrix);
    }
    
    // 计算3x3矩阵的逆（简化实现）
    private int[][] calculate3x3Inverse(int[][] matrix, int detInverse) {
        int[][] adjugate = new int[3][3];
        
        // 计算余子式矩阵
        int[][] cofactor = new int[3][3];
        cofactor[0][0] = (matrix[1][1] * matrix[2][2] - matrix[1][2] * matrix[2][1]) % 26;
        cofactor[0][1] = (-(matrix[1][0] * matrix[2][2] - matrix[1][2] * matrix[2][0])) % 26;
        cofactor[0][2] = (matrix[1][0] * matrix[2][1] - matrix[1][1] * matrix[2][0]) % 26;
        cofactor[1][0] = (-(matrix[0][1] * matrix[2][2] - matrix[0][2] * matrix[2][1])) % 26;
        cofactor[1][1] = (matrix[0][0] * matrix[2][2] - matrix[0][2] * matrix[2][0]) % 26;
        cofactor[1][2] = (-(matrix[0][0] * matrix[2][1] - matrix[0][1] * matrix[2][0])) % 26;
        cofactor[2][0] = (matrix[0][1] * matrix[1][2] - matrix[0][2] * matrix[1][1]) % 26;
        cofactor[2][1] = (-(matrix[0][0] * matrix[1][2] - matrix[0][2] * matrix[1][0])) % 26;
        cofactor[2][2] = (matrix[0][0] * matrix[1][1] - matrix[0][1] * matrix[1][0]) % 26;
        
        // 转置得到伴随矩阵
        for (int i = 0; i < 3; i++) {
            for (int j = 0; j < 3; j++) {
                adjugate[i][j] = cofactor[j][i];
                if (adjugate[i][j] < 0) adjugate[i][j] += 26;
            }
        }
        
        // 乘以行列式逆元
        int[][] inverse = new int[3][3];
        for (int i = 0; i < 3; i++) {
            for (int j = 0; j < 3; j++) {
                inverse[i][j] = (adjugate[i][j] * detInverse) % 26;
            }
        }
        
        return inverse;
    }
    
    // 3. 加密方法
    public String encrypt(String plaintext) {
        // 预处理：去除非字母字符，转大写
        String processedText = preprocessText(plaintext);
        System.out.println("预处理后的文本: " + processedText);
        
        // 分组
        List<int[]> groups = groupText(processedText);
        
        // 加密每组
        StringBuilder ciphertext = new StringBuilder();
        for (int[] group : groups) {
            int[] encryptedGroup = multiplyMatrixVector(keyMatrix, group);
            for (int value : encryptedGroup) {
                ciphertext.append((char) (value + 'A'));
            }
        }
        
        return ciphertext.toString();
    }
    
    // 4. 解密方法
    public String decrypt(String ciphertext) {
        // 分组
        List<int[]> groups = groupText(ciphertext);
        
        // 解密每组
        StringBuilder plaintext = new StringBuilder();
        for (int[] group : groups) {
            int[] decryptedGroup = multiplyMatrixVector(inverseKeyMatrix, group);
            for (int value : decryptedGroup) {
                plaintext.append((char) (value + 'A'));
            }
        }
        
        return plaintext.toString();
    }
    
    // 文本预处理
    private String preprocessText(String text) {
        return text.replaceAll("[^A-Za-z]", "").toUpperCase();
    }
    
    // 文本分组
    private List<int[]> groupText(String text) {
        List<int[]> groups = new ArrayList<>();
        int index = 0;
        
        while (index < text.length()) {
            int[] group = new int[matrixSize];
            for (int i = 0; i < matrixSize; i++) {
                if (index < text.length()) {
                    group[i] = text.charAt(index) - 'A';
                    index++;
                } else {
                    // 填充'X'
                    group[i] = 'X' - 'A';
                }
            }
            groups.add(group);
        }
        
        return groups;
    }
    
    // 矩阵与向量乘法
    private int[] multiplyMatrixVector(int[][] matrix, int[] vector) {
        int[] result = new int[matrixSize];
        for (int i = 0; i < matrixSize; i++) {
            int sum = 0;
            for (int j = 0; j < matrixSize; j++) {
                sum += matrix[i][j] * vector[j];
            }
            result[i] = sum % 26;
            if (result[i] < 0) result[i] += 26;
        }
        return result;
    }
    
    // 打印矩阵
    private void printMatrix(int[][] matrix) {
        for (int i = 0; i < matrix.length; i++) {
            for (int j = 0; j < matrix[i].length; j++) {
                System.out.printf("%2d ", matrix[i][j]);
            }
            System.out.println();
        }
    }
    
    // 主程序
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        
        System.out.print("请输入矩阵大小 (2 或 3): ");
        int size = scanner.nextInt();
        scanner.nextLine(); // 消耗换行符
        
        if (size != 2 && size != 3) {
            System.out.println("只支持2x2或3x3矩阵");
            return;
        }
        
        HillCipher hillCipher = new HillCipher(size);
        
        System.out.print("请输入明文: "); //Information Security
        String plaintext = scanner.nextLine();
        
        String ciphertext = hillCipher.encrypt(plaintext);
        
        // 解密
        String decryptedText = hillCipher.decrypt(ciphertext);
        System.out.println("解密结果: " + decryptedText);
        
        System.out.println("请输入密码:");
        String str1 = scanner.nextLine();
        
        if("Hello World".equals(str1) ) {
        	// 加密
        	System.out.println("加密结果: " + ciphertext);
        	
        }else {
        	System.out.println("密码错误");
        }
        
        
        
    }
}